package io.github.handyang.algorithms.graph;

/**
 * 环检测（图中无自环&无平行边）
 */
public class Cycle {
    private final Graph graph;
    private final boolean[] marked;
    private boolean hasCycle = false;

    public Cycle(Graph graph) {
        this.graph = graph;
        this.marked = new boolean[this.graph.V()];

        for (int i = 0; i < marked.length; i++) {
            if (marked[i]) continue;
            dfs(i, i);
        }
    }

    private void dfs(int start, int prePoint) {
        marked[start] = true;

        for (Integer point : graph.adj(start)) {
            if (!marked[point]) {
                dfs(point, start);
            } else if (prePoint != point) {//这个条件不能判断平行边和自环，所以这个算法至少得3个点构成的环
                hasCycle = true;
            }
        }
    }

    public boolean hasCycle() {
        return hasCycle;
    }
}
